package regexInput;

import java.io.Serializable;
import java.util.ArrayList;

public class NFAtoDFA implements Serializable{
	/**
	 * 
	 */
	private static final long serialVersionUID = 7702384965082901019L;
	//Data Structure for DFA
	private DSTable dfa;
	private DSTable nfa;	//or nfa javaobject
	private ArrayList<TableNode> buffer;	//waiting queue
	private ArrayList<TableNode> global;	//list of all states that are in dfa table
	private ArrayList<String> dfaFinalStates;	//list of dfa final states
	private ArrayList<String> finalStates;	//list of nfa final states
	private int counter;					//DFA state number
	private int dfaRow;						//DFA row number
	public NFAtoDFA(DSTable struct, ArrayList<String> fs){//Input data structure
		finalStates = fs;
		dfaFinalStates = new ArrayList<String>();
		global = new ArrayList<TableNode>();
		buffer = new ArrayList<TableNode>();
		counter = 0;
		nfa = struct;
		dfa = new DSTable();
		ArrayList<String> temp = nfa.getCharClasses(); 	//set the the first row as the char class transitions from the NFA 
		temp.remove(temp.size() - 1);					//minus epsilon transition for DFA
		dfa.setCharClasses(temp);
		toDFA();
	}
	
	/**
	 * goes through the process to create the DFA
	 */
	private void toDFA(){		
		dfaRow = 0;
		
		TableNode tempNode = new TableNode(counter + "", 0);				//initialize what will go in the first row here
		counter++;
		TableNode startNFARow = nfa.getState(0);//get start state of nfa as well as first row of corresponding NFA table

		String id;
		boolean done = false;
		//First get/make the Starting State and any epsilon transitions:
		
		ArrayList<String> temp = startNFARow.getTransitions(nfa.getCharClasses().size() - 1);		//should contain the epsilon transitions
		tempNode.setNFAState(temp);	//do epsilon closeure to complete start state
		
		global.add(tempNode);		//add current working node to global (so that it can state transition to itself)
		dfa.addSetState(tempNode);
		getTransitions(tempNode);		//get transitions for start state
		
		//LOOP START: while buffer is not empty
		while(buffer.size() != 0){
			dfaRow++;
		//Take out first state from buffer
			tempNode = buffer.remove(0);
			dfa.addSetState(tempNode);
		//Trace transitions and put names of states onto table
			getTransitions(tempNode);
		//Check for any newly created states add to buffer	(HANDLED in getTransitions())
			//Check the buffer as well	(HANDLED in getTransitions())
		}
		//LOOP END:
		//RESULT (should be) IS DFA
	}
	
	/**
	 * @param stateList
	 * @return 	the number assigned if found
	 * 			-1 - if not found
	 */
	private int checkExisting(ArrayList<String> stateList){
		boolean existing = false;
		boolean found = false;
		ArrayList<String> temp;
		for(int i = 0; i < global.size(); i++){
			//compare contents, if same return the index the node resides in
			temp = global.get(i).getNFAList();
			if(temp.size() != stateList.size()){
							//cannot be the same if they are of different sizes
			}
			else{
			for(int j = 0; j < temp.size(); j++){
				for(int k = 0; k < stateList.size(); k++){
					if(temp.get(j).equals(stateList.get(k))){
						existing = true;
						k = stateList.size();
					}
				}
				if(existing){
					existing = false; 	//go on
					found = true;
				}
				else{
					j = temp.size();	//skip this one since we can conclude they cannot be the same
					found = false;
				}
			}
			if(found){
				return Integer.parseInt(global.get(i).getName());		//should be equal to the dfa state number we have given it
			}
			}
		}
		return -1;
	}
	
	private void getTransitions(TableNode node){
		TableNode scoutNode;
		TableNode tempNode;
		ArrayList<String> contents;
		ArrayList<String> epsilonContents;
		ArrayList<String> storage = new ArrayList<String>();
		ArrayList<String> tempList = node.getNFAList();		//contains the nfa corresponding nodes/states
		ArrayList<ArrayList<String>> transitionBuffer = new ArrayList<ArrayList<String>>();
		for(int j = 0; j < nfa.getCharClasses().size() - 1; j++){	//iterate over all transitions, exclude epsilon transitions in this pass
			transitionBuffer.add(new ArrayList<String>());	//initalize slot
			for(int i = 0; i < tempList.size(); i++){	//go through the old nfa states in current node
				scoutNode = nfa.getState(Integer.parseInt((tempList.get(i))));	//corresponding state in NFA table
				contents = scoutNode.getTransitions(j);							//corresponding transitions of that state in NFA table
				for(String element : contents){
					if(element.equals("-1")){	//check for -1
					}
					else{
					epsilonContents = nfa.getState(Integer.parseInt(element)).getTransitions(nfa.getCharClasses().size() - 1); //get epsilon trans
					for(String epEle : epsilonContents){
						if(!storage.contains(epEle)){
							storage.add(epEle);	
						}
					}
				}
				}
			}
			if(!storage.isEmpty()){
				int count = checkExisting(storage);
				
				if(count >= 0){
					transitionBuffer.get(j).add(count + "");	//associate count as a transition in the buffer
				}
				else{ 
					tempNode = new TableNode(counter + "", - 1);	//Make a new node to be placed into buffer
					tempNode.setNFAState(storage);
					if(isFinalState(storage)){
						tempNode.setState(1);
						dfaFinalStates.add(counter + "");
					}
					buffer.add(tempNode);
					global.add(tempNode);
					transitionBuffer.get(j).add(counter + "");	//put it in buffer
					counter++;
				}
				storage = new ArrayList<String>();
			}
			else{	//there was no transitions found
				transitionBuffer.get(j).add("-1");
			}
		}
		dfa.getState(dfaRow).setTransitions(transitionBuffer);	//set into the respected row
	}
	
	private boolean isFinalState(ArrayList<String> list){
		for(int i = 0; i < list.size(); i++){	//if one of these states are a final state, the whole thing is final
			for(int j = 0; j < finalStates.size(); j++){
				if(list.get(i).equals(finalStates.get(j))){
					return true;
				}
			}
		}
		return false;
	}
	
	public DSTable getDFA(){
		return dfa;
	}
	
	
	public String printFinalStates(){
		String s = "";
		for(String element : dfaFinalStates){
			s += element + "  ";
		}
		return s;
	}
	public String toString(){
		String s = "";
		s += dfa.toString();
		return s;
	}
}
